一、ProNE [2019]

《ProNE: Fast and Scalable Network Representation Learning》

1. 在过去的几年里，representation learning 为网络挖掘和分析提供了一种新的范式。representation learning 的目标是将网络结构投影到一个连续的 embedding 空间，同时保持网络的某些属性。广泛的研究表明，学到的 embedding 可以使得众多的数据挖掘任务受益。

   network embedding 的最新进展大致可以分为三类：

   • 基于矩阵分解的方法，如 SocDim, GraRep, HOPE, NetMF。

   • 基于 SkipGram 的模型，如 DeepWalk, LINE, node2vec。

   • 基于图神经网络（graph neural network: GNN）的方法，如 Graph Convolution, GraphSage, Graph Attention。

   通常，前两种方法预训练的 embedding 被输入到下游任务的学习模型中。因此，高效地生成有效的 network embedding 从而服务于大型网络application 至关重要。然而，大多数现有模型都聚焦于提高 embedding 的效果（effectiveness ），使得模型的效率（efficiency ）和可扩展性（scalability ）受到限制。例如，在基于分解的模型中，GraRep 的时间复杂度为 $O(n^3)$$O(n^3)$，其中 $n$$n$ 为网络中的节点数量，这使得在大型网络中的计算成本太高。在基于 SkipGram 的模型中，当使用默认超参数时，在现代服务器上使用 20 个线程来学习一亿个节点、五亿条边的网络的 embedding，LINE 将花费数周时间，DeepWalk/node2vec 将花费数月时间。

   为了解决当前工作的效率和可扩展性的限制，论文《ProNE: Fast and Scalable Network Representation Learning》 提出了一种高效的、且可扩展的 network embedding 算法 ProNE。ProNE 的总体思想是：首先以有效的方式初始化 network embedding，然后增强这些 embedding 的表达能力。受大多数真实网络的长尾分布及其产生的网络稀疏性（network sparsity） 的启发，第一步是通过将 network embedding 形式化为稀疏矩阵分解来实现。第二步是利用高阶 Cheeger 不等式对初始化的 embedding 进行谱域传播，目标是捕获网络的局部平滑（localized smoothing ）信息和全局聚类（global clustering ）信息。

   这种设计使得 ProNE 成为一个速度极快的 embedding 模型，同时保持效果上的优势。论文在五个真实世界网络和一组随机网络上进行了实验。大量实验表明，单线程 ProNE 模型要比具有 20 个线程的、流行的 network embedding benchmark （包括 DeepWalk, LINE, node2vec ）快大约 10 ~ 400 倍，如下图所示。论文的可扩展性分析表明，ProNE 的时间成本与network volume 和 network density 呈线性相关，使得 ProNE 可以扩展到数十亿规模的网络。事实上，通过仅使用一个线程，ProNE 只需要 29 个小时来学习上述一亿个节点的网络的 embedding 。注意，ProNE 也很容易并行化。

   

   除了效率和可扩展性优势之外，ProNE 在多标签节点分类任务的所有数据集中也始终优于所有 baseline。更重要的是，ProNE 中的第二步（即，谱域传播 spectral propagation ）是增强 network embedding 的通用框架。通过将 DeepWalk, LINE, node2vec, GraRep, HOPE 生成的 embedding 作为输入，论文的谱域传播策略在一秒钟内为所有这些 embedding 进行了增强，并带来了平均 +10% 的相对提升。

   这篇论文的基本思想是：首先训练一个 initial embedding ，然后通过消息传递机制在network 上传播这个 initial embedding 从而 refine 。它复用了标签传播的思想，并没有太大的创新。至于 initial embedding 方法可以有多种选择，不一定必须采用论文中提到的方法。

2. 相关工作：最近出现的 network embedding 很大程度上是由 SkipGram 在自然语言和网络挖掘中的应用所引发的。network embedding 的历史可以追溯到谱聚类（ spectral clustering ）和社交维度学习（ social dimension learning ）。在 network embedding 的发展过程中，大多数方法旨在隐式地或显式地建模节点之间分布式（distributional） 的相似性。

   受word2vec 模型的启发，人们已经提出了一系列基于 SkipGram 的 embedding 模型，用于将网络结构编码为连续空间，如 DeepWalk, LINE, node2vec 。最近的一项研究 《Neural word embedding as implicit matrix factorization》 表明，基于 SkipGram 的 network embedding 可以理解为隐式矩阵分解。此外，受到该研究的启发，《Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec》 提出了 NetMF 模型来执行显式矩阵分解从而学习 network embedding 。NetMF 与我们模型的区别在于：NetMF 要分解的矩阵是稠密矩阵，其构造和分解涉及到 $O(n^3)$$O(n^3)$ 时间复杂度的计算（$n$$n$ 为网络节点数量），而我们的 ProNE 模型将 network embedding 形式化为 $O(|\mathcal{E}|)$$O(|\mathcal E|)$ 的稀疏矩阵分解（$|\mathcal{E}|$$|\mathcal E|$ 为网络中边的数量）。

   其它一些近期的、基于矩阵分解的 network embedding 模型包括 GraRep 和 HOPE 。谱域的network emebdding 与谱域降维方法有关，例如 Isomap、Laplacian Eigenmap 、spectral clustering 。这些基于矩阵分解的方法通常需要昂贵的计算、以及过多的内存消耗，因为它们的时间复杂度和空间复杂度都很高。

   另一个重要的工作方向是将图谱（ graph spectral ）推广到监督的 graph learning 中，如图卷积网络（ graph convolution network: GCN ）。在 GCN 中，卷积操作是在谱空间中定义的，参数化的 filter 是通过反向传播来学习的。与它们不同的是，我们的 ProNE 模型具有一个带通滤波器 （band-pass filter ）（该滤波器的参数是人为设定的，因此不需要学习），该滤波器同时结合了空间局部平滑（spatial locality smoothing ）和全局聚类（global clustering ）两个特点。此外，ProNE 是一种无监督且任务无关的模型，旨在预训练通用的 embedding，而大多数 GCN 是以辅助特征（例如由 ProNE 学到的 network embedding ）作为输入的监督学习。

1.1 模型

1. 定义图 $G=(\mathcal{V},\mathcal{E})$$G=(\mathcal V,\mathcal E)$ ，其中 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n\}$ 为所有节点集合，$\mathcal{E}=\{e_{i,j}\}$$\mathcal E=\{e_{i,j}\}$ 为所有边的集合。定义 $\mathbf{A}$$\mathbf A$ 为图 $G$$G$ 的邻接矩阵。定义度矩阵（ degree matrix ）为对角矩阵 $\mathbf{D}=\text{diag}(D_{i,i})$$\mathbf D = \text{diag}(D_{i,i})$ ，其中 $D_{i,i}=\sum _j{A}_{i,j}$$D_{i,i} = \sum_j A_{i,j}$ 。这里我们仅考虑无向图（不考虑有向图），边可以是带权重的也可以是无权重的。

   给定网络 $G=(\mathcal{V},\mathcal{E})$$G=(\mathcal V,\mathcal E)$ ， network embedding 的目标是学习一个映射函数 $f:\mathcal{V}\to {\mathbb{R}}^d,d\ll n$$f: \mathcal V\rightarrow \mathbb R^d,d\ll n$ ，从而将每个节点 $v_i$$v_i$ 映射成一个低维向量 ${\overrightarrow{\mathbf{v}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec v}_i\in \mathbb R^d$ ，其中 ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 捕获了网络结构信息 。广泛的研究表明，学到的 node representation 可以使得各种下游的图挖掘任务受益。然而，目前的一个主要挑战是：大多数network embedding 模型处理大规模网络在计算上不可行。例如，即使使用 20 个线程，DeepWalk 学习一个包含一亿节点的稀疏图的embedding 需要耗时几个月。

2. 我们提出的ProNE是一种用于大规模网络的 embedding 的非常快速且可扩展的模型，它由两个步骤组成，如下图所示：

   • 首先 ProNE 将network embedding 建模为稀疏矩阵分解，从而获得节点的有效初始 embedding。

   • 然后 ProNE 利用高阶 Cheeger 不等式来调制（ modulate ）谱域空间，并在调制后的谱域空间传播学到的 embedding ，从而集成了局部平滑信息和全局聚类信息。

   

1.1.1 稀疏矩阵分解

1. 分布式假设（ distributional hypothesis） 启发了最近出现的 word embedding 和 network embedding。这里我们展示了如何将基于分布式相似性（ distributional similarity-based ）的 network embedding 形式化为矩阵分解。

2. network embedding 作为稀疏矩阵分解：通常我们利用结构上下文（structural context ）来建模节点相似性。我们建议利用最简单的结构，即 edge ，来表示 node-context 的 pair 对。然后我们得到了 node-context 集合 $\mathcal{D}$$\mathcal D$ ，根据定义有 $\mathcal{D}=\mathcal{E}$$\mathcal D = \mathcal E$ 。公式化地，我们给定节点 $v_i$$v_i$ 的条件下， context $v_j$$v_j$ 出现的概率为：${\hat{p}}_{i,j}=\sigma ({\overrightarrow{\mathbf{c}}}_j\cdot {\overrightarrow{\mathbf{v}}}_i)$$\hat p_{i,j} = \sigma(\mathbf{\vec c}_j \cdot \mathbf{\vec v}_i)$ 。其中： $\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数， ${\overrightarrow{\mathbf{c}}}_j$$\mathbf{\vec c}_j$ 为节点 $v_j$$v_j$ 作为上下文时的 context embedding ； ${\overrightarrow{\mathbf{v}}}_i$$\mathbf{\vec v}_i$ 为节点 $v_i$$v_i$ 的 embedding 。

   这里我们的上下文只考虑直接相连的节点（即，随机游走序列中的上下文窗口大小为 1 ）。

   考虑所有的边，则损失函数为 $\mathcal{L}=-\sum _{(v_i,v_j)\in \mathcal{D}}\log {\hat{p}}_{i,j}$$\mathcal L = -\sum_{(v_i,v_j)\in \mathcal D} \log \hat p_{i,j}$ 。考虑到不同节点的 degree 不同，因此我们对损失函数进行加权：

   $$\mathcal{L}=-\sum _{(v_i,v_j)\in \mathcal{D}}{p}_{i,j}\times \log {\hat{p}}_{i,j}$$

   其中 $p_{i,j}=A_{i,j}/D_{i,i}$$p_{i,j} = A_{i,j}/ D_{i,i}$ 表示边 $(v_i,v_j)$$(v_i,v_j)$ 的权重占 $v_i$$v_i$ 所有边的权重的比例，比例越大则 ${\hat{p}}_{i,j}$$\hat p_{i,j}$ 的预估越重要。

   上述目标函数存在一个平凡解：对于任意 $v_i,v_j$$v_i,v_j$ 都有 ${\hat{p}}_{i,j}=1$$\hat p_{i,j} = 1$ 。即，对于任意一对节点 $(v_i,v_j)$$(v_i,v_j)$ ，模型预估它们之间存在边。这一平凡解的本质原因是：$\mathcal{L}$$\mathcal L$ 只有“正边”、没有“负边”（即不存在的链接）。因此我们将损失函数修改为：最大化“正边”概率，且最小化“负边”概率。

   假设负采样比例为 $\lambda$$\lambda$ ，采样到 $v_j$$v_j$ 作为 ”负边“ 上下文的概率为 $P_{\mathcal{D},j}$$P_{\mathcal D,j}$ ，则有：

   $$\mathcal{L}=-\sum _{(v_i,v_j)\in \mathcal{D}}(p_{i,j}\times \log \sigma ({\overrightarrow{\mathbf{c}}}_j\cdot {\overrightarrow{\mathbf{v}}}_i)+\sum _{k=1,v_k\in \mathcal{V}}^{k=\lambda }{P}_{\mathcal{D},k}\times \log \sigma (-{\overrightarrow{\mathbf{c}}}_k\cdot {\overrightarrow{\mathbf{v}}}_i))$$

   其中 ${\mathcal{P}}_{\mathcal{D},j}$$\mathcal P_{\mathcal D,j}$ 定义为：

   $${\mathcal{P}}_{\mathcal{D},j}\propto {\left(\sum _{v_i:(v_i,v_j)\in \mathcal{D}}{p}_{i,j}\right)}^{\alpha }={\left(\sum _{v_i:(v_i,v_j)\in \mathcal{D}}\frac{A_{i,j}}{D_{i,i}}\right)}^{\alpha }$$

   $\alpha =1.0$$\alpha = 1.0$ 或者 $0.5$$0.5$ 。

   根据偏导数为零 $\frac{\partial \mathcal{L}}{\partial ({\overrightarrow{\mathbf{c}}}_j\cdot {\overrightarrow{\mathbf{v}}}_i)}=0$$\frac{\partial \mathcal L}{\partial (\mathbf{\vec c}_j \cdot \mathbf{\vec v}_{i })} = 0$ ，我们得到：

   $${\overrightarrow{\mathbf{c}}}_j\cdot {\overrightarrow{\mathbf{v}}}_i=\log p_{i,j}-\log (\lambda {\mathcal{P}}_{\mathcal{D},j}),(v_i,v_j)\in \mathcal{D}$$

   定义邻近性矩阵（proximity matrix ） $\mathbf{M}$$\mathbf M$ 为：

   $$\begin{array}{c}{M}_{i,j}=\{\begin{array}{ll}\log p_{i,j}-\log (\lambda {\mathcal{P}}_{\mathcal{D},j}),& (v_i,v_j)\in \mathcal{D}\\ 0,& (v_i,v_j)\notin \mathcal{D}\end{array}\end{array}$$

   因此基于分布式相似性的 network embedding 的目标函数等价于对 $\mathbf{M}$$\mathbf M$ 进行矩阵分解。我们使用谱方法，截断的奇异值分解（truncated Singular Value Decomposition:tSVD ），来求解，即：

   $$\mathbf{M}\simeq {\mathbf{U}}_d{\mathrm{\Sigma }}_d{\mathbf{V}}_d^{\mathrm{\top }}$$

   其中： ${\mathrm{\Sigma }}_d$$\Sigma_d$ 为 top d 个奇异值组成的对角矩阵； ${\mathbf{U}}_d$$\mathbf U_d$ 和 ${\mathbf{V}}_d$$\mathbf V_d$ 分别为奇异值分解中对应的分解矩阵的前 d 列。

   最终 ${\mathbf{U}}_d{\mathrm{\Sigma }}_d^{1/2}$$\mathbf U_d \Sigma_d^{1/2}$ 为 embedding 矩阵，第 $i$$i$ 行表示节点 $v_i$$v_i$ 的 embedding 向量。

   可以看到，由于 $\mathbf{M}$$\mathbf M$ 仅在“正边”上非零，从而使得 $\mathbf{M}$$\mathbf M$ 为一个稀疏矩阵。

3. 用于快速 embedding 的稀疏化随机 tSVD ：虽然可以通过矩阵分解来求解 network embedding，但是在大规模矩阵上执行 tSVD 的时间复杂度、空间复杂度仍然非常高。为了实现快速的 network emebdding ，我们建议使用随机 tSVD。根据随机矩阵理论，该方法可以大大加快 tSVD 的速度，并具有理论的近似保证。

   • 首先寻找一个矩阵 $\mathbf{Q}\in {\mathbb{R}}^{n\times d}$$\mathbf Q\in \mathbb R^{n\times d}$，它包含 $d$$d$ 个正交列，使得 $\mathbf{M}\simeq \mathbf{Q}{\mathbf{Q}}^{\mathrm{\top }}\mathbf{M}$$\mathbf M\simeq \mathbf Q\mathbf Q^\top \mathbf M$ 。

   • 假设找到这样的矩阵 $\mathbf{Q}$$\mathbf Q$，定义 $\mathbf{H}={\mathbf{Q}}^{\mathrm{\top }}\mathbf{M}\in {\mathbb{R}}^{d\times n}$$\mathbf H = \mathbf Q^\top\mathbf M\in \mathbb R^{d\times n}$ ，它是一个小得多的矩阵，并可以通过标准的 SVD 进行高效地分解。

   • 假设已经得到分解 $\mathbf{H}={\mathbf{S}}_d{\mathrm{\Sigma }}_d{\mathbf{V}}_d^{\mathrm{\top }}$$\mathbf H = \mathbf S_d\Sigma_d\mathbf V_d^\top$， 则最终有 $\mathbf{M}\simeq \mathbf{Q}{\mathbf{Q}}^{\mathrm{\top }}\mathbf{M}=(\mathbf{Q}{\mathbf{S}}_d){\mathrm{\Sigma }}_d{\mathbf{V}}_d^{\mathrm{\top }}$$\mathbf M\simeq \mathbf Q\mathbf Q^\top \mathbf M =( \mathbf Q\mathbf S_d)\Sigma_d\mathbf V_d^\top$ 。因此最终节点的 embedding 矩阵为 $(\mathbf{Q}{\mathbf{S}}_d){\mathrm{\Sigma }}_d^{1/2}$$( \mathbf Q\mathbf S_d)\Sigma_d^{1/2}$ ，其中 ${\mathbf{S}}_d\in {\mathbb{R}}^{d\times d}$$\mathbf S_d\in \mathbb R^{d\times d}$ 。

   随机矩阵理论使我们能够有效地找到 $\mathbf{Q}$$\mathbf Q$ ：

   • 首先生成一个 $n\times d$$n\times d$ 维的高斯随机矩阵 $\mathbf{\Omega }\in {\mathbb{R}}^{n\times d}$$\mathbf\Omega\in \mathbb R^{n\times d }$，其中 ${\mathrm{\Omega }}_{i,j}\in \mathcal{N}(0,\frac{1}{d})$$\Omega_{i,j}\in \mathcal N(0,\frac 1d)$ 。

   • 然后定义矩阵 $\mathbf{Y}=\mathbf{M}\mathbf{\Omega }$$\mathbf Y = \mathbf M \mathbf\Omega$ ，并对 $\mathbf{Y}$$\mathbf Y$ 进行 QR 分解：$\mathbf{Y}=\mathbf{Q}\mathbf{R}$$\mathbf Y = \mathbf Q\mathbf R$ 。这个矩阵 $\mathbf{Q}\in {\mathbb{R}}^{n\times d}$$\mathbf Q\in \mathbb R^{n\times d}$ 就是我们希望找到的。

   已有工作证明，基于 SkipGram 的 network embedding 模型等价于隐式的矩阵分解，但是分解的是一个稠密矩阵，其计算复杂度为 $O(n^3)$$O(n^3)$ 。而我们这里涉及的是一个稀疏矩阵分解，计算复杂度为 $O(|\mathcal{E}|)$$O(|\mathcal E|)$ 。

1.1.2 embedding 谱域传播

1. 与 DeepWalk,LINE 等其它流行方法类似，通过稀疏矩阵分解得到的 embedding 仅捕获局部结构信息。为了进一步集成全局网络属性（如社区结构），我们提出在谱域中传播 embedding 。注意，该策略是通用的，也可用于提升现有的 embedding 模型。

2. network embedding 与 graph spectrum 和 graph partition 的关联：高阶 Cheeger 不等式表明，graph spectral 中的特征值与网络的空间局部平滑（ spatial locality smoothing ）、全局聚类（global clustering ）密切相关。 我们首先介绍公式，然后展示如何帮助增强 network embedding 。

   在图论中，归一化的图拉普拉斯矩阵定义为：

   $$\mathbf{L}=\mathbf{I}-{\mathbf{D}}^{-1}\mathbf{A}$$

   $\mathbf{L}$$\mathbf L$ 可以分解为 $\mathbf{L}=\mathbf{U}\mathrm{\Lambda }{\mathbf{U}}^{-1}$$\mathbf L = \mathbf U \Lambda \mathbf U^{-1}$ ，其中：

   • $\mathrm{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_n)$$\Lambda = \text{diag}(\lambda_1,\cdots,\lambda_n)$ ， $0={\lambda }_1\le \cdots \le {\lambda }_n$$0=\lambda_1\le \cdots\le \lambda_n$ 为 $\mathbf{L}$$\mathbf L$ 的特征值。

   • $\mathbf{U}$$\mathbf U$ 为特征向量组成的矩阵，第 $i$$i$ 列为 ${\lambda }_i$$\lambda_i$ 对应的特征向量。

   给定信号 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$，图上的傅里叶变换为：$\widehat{\overrightarrow{\mathbf{x}}}={\mathbf{U}}^{-1}\overrightarrow{\mathbf{x}}$$\hat{\mathbf{\vec x}} = \mathbf U^{-1} \mathbf{\vec x}$ ，图上的傅里叶逆变换为： $\overrightarrow{\mathbf{x}}=\mathbf{U}\widehat{\overrightarrow{\mathbf{x}}}$$\mathbf{\vec x}= \mathbf U \hat{\mathbf{\vec x}}$ 。因此图上的信号传播 ${\mathbf{D}}^{-1}\mathbf{A}\overrightarrow{\mathbf{x}}$$\mathbf D^{-1}\mathbf A \mathbf{\vec x}$ 可以理解为：首先将 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 通过傅里叶变换转换到谱域，然后在谱域根据拉普拉斯矩阵的特征值进行缩放，最后把谱域缩放后的信号逆变换为空域。

   图上的信号传播 ${\mathbf{D}}^{-1}\mathbf{A}\overrightarrow{\mathbf{x}}$$\mathbf D^{-1}\mathbf A \mathbf{\vec x}$ 其物理意义为：信号沿着边进行流动，每条边的流量为 $\frac{A_{i,j}}{D_{i,i}}$$\frac{A_{i,j}}{D_{i,i}}$ 。

   给定图 $G$$G$ 的一个划分 $\mathcal{S}\subseteq \mathcal{V}$$\mathcal S\sube \mathcal V$，我们通过定义 Cheeger 常数来衡量图的划分效果：

   $$C_{\mathcal{S}}=\frac{|\mathcal{E}(\mathcal{S})|}{min(\text{vol}(\mathcal{S}),\text{vol}(\mathcal{V}-\mathcal{S}))}$$

   其中：$\mathcal{E}(\mathcal{S})$$\mathcal E(\mathcal S)$ 为一个点在 $\mathcal{S}$$\mathcal S$ 内、另一个点在 $\mathcal{S}$$\mathcal S$ 外的边的集合，$\text{vol}(S)$$\text{vol}(S)$ 为节点集合 $\mathcal{S}$$\mathcal S$ 中所有节点的 degree 之和。

   Cheeger 常数的物理意义为：随机选择 $\mathcal{S}$$\mathcal S$ 或者 $\mathcal{V}-\mathcal{S}$$\mathcal V-\mathcal S$ 中节点的一条边，这条边扩展到集合外的概率。

   给定图 $G$$G$ 的一个 k-way 划分：

   $$\begin{array}{c}{\mathcal{S}}_1\cup {\mathcal{S}}_2\cup \cdots \cup {\mathcal{S}}_k=\mathcal{V}\\ {\mathcal{S}}_1\cap {\mathcal{S}}_2={\mathcal{S}}_1\cap {\mathcal{S}}_3=\cdots ={\mathcal{S}}_{k-1}\cap {\mathcal{S}}_k=\varphi \end{array}$$

   定义 k 阶 Cheeger 常数为 ${\rho }_G(k)=max\{C_{{\mathcal{S}}_i}\}$$\rho_G(k) = \max\{C_{\mathcal S_i} \}$ ，它反映了将图划分为 $k$$k$ 个部分的效果，取值越小则说明划分得越好。高阶 Cheeger 不等式给出了graph partition 和 graph spectrum之间的联系：

   $$\frac{{\lambda }_k}{2}\le {\rho }_G(k)\le O(k^2)\sqrt{{\lambda }_k}$$

   可以看出：

   • 无向图中连通分量的数量，等于拉普拉斯矩阵中取值为零的特征值数量。这可以通过设置 ${\lambda }_k=0$$\lambda_k =0$ 从而得到 ${\rho }_G(k)=0$$\rho_G(k)=0$ 来导出。

   • 小特征值通过将网络划分为几个大的部分，从而控制网络的全局聚类效果；大特征值通过将网络划分为很多小部分，从而控制网络的局部平滑效果。

     这启发我们通过在划分后的（或者说调制后的）网络的谱域中传播 embedding，从而将全局信息和局部信息集成到 network embedding 中。

   假设 node embedding 矩阵为 ${\mathbf{R}}_d$$\mathbf R_d$ ，经过谱域空间传播后的 embedding 为：

   $${\mathbf{R}}_d\leftarrow (\mathbf{I}-\tilde{\mathbf{L}}){\mathbf{R}}_d$$

   其中：

   • $\tilde{\mathbf{L}}=\mathbf{U}g(\mathrm{\Lambda }){\mathbf{U}}^{-1}$$\tilde{\mathbf L} = \mathbf U g(\Lambda) \mathbf U^{-1}$ 为通过函数 $g$$g$ 调制的拉普拉斯矩阵， $g$$g$ 称作谱域调制器（ spectral modulator ）。

   • $(\mathbf{I}-\tilde{\mathbf{L}})$$(\mathbf I - \tilde{\mathbf L})$ 为调制后的网络。当 $g$$g$ 为恒等映射时，上式退化为 $\mathbf{I}-\mathbf{L}={\mathbf{D}}^{-1}\mathbf{A}$$\mathbf I - \mathbf L = \mathbf D^{-1} \mathbf A$ 。

   为同时考虑全局结构信息和局部结构信息，我们选择谱域调制器为：

   $$g(\lambda )=\exp (-\frac{1}{2}((\lambda -\mu {)}^2-1)\theta )$$

   其中 $\mu$$\mu$ 和 $\theta$$\theta$ 为参数。$g(\lambda )$$g(\lambda)$ 可以被认为是带通滤波器，它将某个范围内的特征值通过，并衰减范围外的特征值。因此 ${\rho }_G(k)$$\rho_G(k)$ 针对 top 最大和 top 最小的特征值进行衰减，分别导致放大局部网络信息和全局网络信息。调制的拉普拉斯矩阵为：$\tilde{\mathbf{L}}=\mathbf{U}\text{diag}(g({\lambda }_1),\cdots ,g({\lambda }_n)){\mathbf{U}}^{\mathrm{\top }}$$\tilde{\mathbf L} = \mathbf U\text{diag}(g(\lambda_1),\cdots,g(\lambda_n)) \mathbf U^\top$ 。

   为什么选择这种结构的谱域调制器，作者并未说明原因。另外，是否可以考虑简单地邻域聚合方式来 refine embedding 。

   注意：

   • 带通滤波器是通用的谱域网络调制器，也可以使用其它类型的滤波器。

   • 可以利用截断的切比雪夫多项式来避免求解 $\tilde{\mathbf{L}}$$\tilde{\mathbf L}$ 的显式特征值分解和傅里叶变换。

   • 为了保持由稀疏 tSVD 实现的原始embedding 空间的正交性，我们再次在 ${\mathbf{R}}_d$$\mathbf R_d$ 上应用 SVD 。

3. 算法复杂度：

   • 对 $\mathbf{H}$$\mathbf H$ SVD 分解的算法复杂度为 $O(n\times d^2)$$O(n\times d^2)$ ，对 $\mathbf{Y}$$\mathbf Y$ 的 QR 分解的算法复杂度为 $O(n\times d^2)$$O(n\times d^2)$ 。

   • 由于 $|\mathcal{E}|\ll n\times n$$|\mathcal E|\ll n\times n$ ，因此 $\mathbf{M}$$\mathbf M$ 是一个稀疏矩阵，上述对 $\mathbf{M}$$\mathbf M$ 的乘法的计算复杂度为 $O(|\mathcal{E}|)$$O(|\mathcal E|)$ 。

   因此第一步稀疏矩阵分解的算法复杂度为 $O(n\times d^2+|\mathcal{E}|)$$O(n\times d^2 + |\mathcal E|)$ 。当使用切比雪夫多项式来近似 $\tilde{\mathbf{L}}$$\tilde{\mathbf L}$ 后，第二步embedding 谱域传播的计算复杂度为 $O(k\times |\mathcal{E}|+n\times d^2)$$O(k\times |\mathcal E| + n\times d^2)$ 。总之，ProNE 的计算复杂度为 $O(n\times d^2+k\times |\mathcal{E}|)$$O(n\times d^2 + k\times |\mathcal E|)$ ，$k$$k$ 为切比雪夫多项式的阶数。ProNE 的空间复杂度为 $O(n\times d+|\mathcal{E}|)$$O(n\times d + |\mathcal E|)$ 。

4. 并行性：ProNE 计算的主要时间消耗在稀疏矩阵乘法上，用单线程来处理足够高效，因此ProNE 主要是单线程的。另外，目前稀疏矩阵乘法的并行化已经取得了一些进展，我们预期将来可以通过多线程的稀疏矩阵乘法进一步提升ProNE 的训练效率。

1.2 实验

1. 数据集：我们使用五个广泛使用的数据集来证明 ProNE 的有效性，另外我们还使用一组人工合成网络来评估其效率和可扩展性。

   • BlogCatalog 数据集：一个社交博客网络，其中博主的兴趣作为label 。

   • Wiki 数据集： Wikipedia dump 文件前一百万个字节中的单词共现网络，其中节点标签是单词的的词性 tag 。

   • PPI 数据集：一个 PPI 网络的子集，其中节点标签是从基因组中提取的，代表生物学状态。

   • DBLP 数据集：一个学术引文网络，节点代表作者，会议conference 为标签。

   • YouTube 数据集：一个 YouTube 用户之间的社交网络，其中节点标签代表基于所喜欢视频类型的用户分组。

   

2. baseline 方法：我们将 ProNE 和流行的 baseline 比较，其中包括基于 SkipGram 的 方法（DeepWalk, LINE, node2vec ），以及基于矩阵分解的方法（GraRep, HOPE ）。

   我们并未考虑基于卷积的方法，因为大多数基于卷积的方法都是监督的或半监督的，这要求额外的标签信息。

3. 配置：

   • 为进行公平比较，所有方法的 embedding 维度为 $d=128$$d=128$ 。对其它超参数，我们使用原始论文中的值。

   • 对于 DeepWalk,node2vec，我们选择窗口大小为 10，每个节点开始的随机游走序列的数量为 10， 随机游走序列长度为 40 。

   • node2vec 中的参数 $p,q$$p,q$ 的搜索空间为 {0.25,0.50,1,2,4} 。

   • 对于 LINE ，负采样系数为 $k=5$$k=5$ 。总的样本量为 $T=r\times t\times |\mathcal{V}|$$T=r\times t\times |\mathcal V|$ 。

   • 对于 GraRep，为公平起见，拼接的 embedding 维度为 $d=128$$d=128$ 。

   • 对于 HOPE， $\beta$$\beta$ 根据作者的代码来计算，并从 (0,1) 之间搜索最佳的值。

   • 对于 ProNE，切比雪夫展开项的数量 $k=10$$k=10$ ， $\mu =0.1$$\mu = 0.1$， $\theta =0.5$$\theta = 0.5$ 。

   运行配置：在 Intel Xeno(R) CPU E5-4650(2.70GHz) ，以及 1T RAM 的 Red Hat server 上运行。

4. 评估方式：我们随机抽取不同比例的标记节点从而训练 liblinear 分类器，并将剩余的标记节点用于测试。我们重复训练和预测十次，报告平均的 Micro-F1 。Macro-F1 的结果也类似，但是由于篇幅有限我们并未显示。

   我们根据 wall-clock 时间来评估算法效率，并通过多种规模的网络中的学习时间来分析 ProNE 的可扩展性。

5. 效率：我们比较了不同方法的训练时间，并展示了 ProNE 的可扩展性，如下图所示（单位为秒）。我们仅给出最快的三个 baseline 方法，因为矩阵分解的baseline 方法 GraRep, HOPE 比它们要慢得多。

   注意：所有baseline 都使用了 20 个线程，而 ProNE 仅使用单个线程。

   结论：单线程 ProNE 模型比 20 线程的 LINE, DeepWalk, node2vec 模型快 10~400 倍，也远远超越了其它矩阵分解方法。

   

6. 可扩展性：我们通过人工合成网络来评估 ProNE 的可扩展性。首先我们生成节点 degree 固定为 10 的随机图，节点规模从 1000 到 1 亿。

   • 图 (a) 给出不同大小随机图上 ProNE 的学习时间，这表明 ProNE 的时间代价随着网络规模的增加而线性增加。

     我们在图上也标注出 ProNE 在五个真实数据集上的学习时间，其趋势也是和网络规模呈线性。另外，蓝色曲线表示 ProNE 的稀疏矩阵分解sparse matrix factorization:SMF 的时间代价。

   • 图 (b) 给出了 ProNE 在固定大小的 1 万个节点上，且节点 degree 从 100 到 1000 之间变化的随机图上的学习时间。可以看到：ProNE 的学习效率和网络密度线性相关。

   结论：ProNE 是一种可扩展的 network embedding 方法，它可以处理大规模、稠密的网络。

   

7. 效果：我们在下表给出了不同模型预测的效果（给出了Micro-F1 的均值和标准差）。除了 ProNE，我们还报告了 ProNE 中由稀疏矩阵分解 SMF 步骤生成的初始 embedding 结果。另外对于 YouTube，node2vec 在五天内无法完成，而 HOPE,GraRep 由于内存消耗太多而无法处理。

   结论：

   • ProNE 在五个数据集中始终比 baseline 效果更好，这证明了其有效性。

   • ProNE 中第一步使用的简单稀疏矩阵分解 SMF 的效果与 baseline 相比相差无几甚至更好。随着谱域传播技术的进一步结合，由于有效地建模了局部结构平滑信息和全局聚类信息，ProNE 在所有 baseline 中产生了最佳性能。

   

8. 用于 embedding 增强的谱域传播：最后我们将 DeepWalk, LINE, node2vec, GraRep, HOPE 学到的 embedding 输入到 ProNE 的谱域传播步骤中。下图显示了 Wiki 上的原始结果和增强结果（称作 ProBaseline ），说明了 Pro 版本对所有五个 baseline 的显著改进。平均而言，我们的谱域传播策略可以为所有方法提供 +10% 的相对提升，例如HOPE 的改善为 25% 。另外，所有增强实验都在1 秒钟内完成。

   结论：ProNE 的谱域传播是有效的，并且是改善 network embedding 的通用且高效策略。